/*
如果正整数可以被 A 或 B 整除，那么它是神奇的。

返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。

提示：

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000
*/
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
class Solution
{
public:
    int gcd(int a, int b)
    {
        int temp = a;
        int t = a / b;
        int r = a - b * t;
        if (r == 0)
        {
            return b;
        }
        return gcd(b,r);
    }
    int nthMagicalNumber(int n, int a, int b)
    {
        if (b > a)
        {
            swap(a, b);
        }
        int g = gcd(a, b);
        int groupNum = a / g + b / g - 1;
        int CONST_MOL = 1e9 + 7;
        long long ans = n / groupNum;
        ans = (ans * (a / g)) % CONST_MOL;
        ans = (ans * b) % CONST_MOL;
        int remain = n % groupNum;
        if(remain == 0){
            return ans;
        }
        int group = ceil(1.0 * a / b);
        int heads[2] = {a, b};
        for (int i = 0; i < remain - 1; ++i) {
            if (heads[0] <= heads[1])
                heads[0] += a;
            else
                heads[1] += b;
        }
        ans = (ans +min(heads[0],heads[1])) % CONST_MOL;
        return ans;
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    int N = 4;
    int A = 2;
    int B = 3;
    // cout << s.gcd(12,8) << endl;
    cout << s.nthMagicalNumber(N, A, B) << endl;
    return 0;
}
